package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

/**
 * @author flutterdash@qq.com
 * @since 2021/3/25 21:53
 */
public class P213 {

    /**
     * [1, 2, 3, 1]
     * [1, 2, 4]     MAX: 4
     *    [2, 3, 3]  MAX: 3
     *               MAX: 4
     *
     *    4, 3, 2, 4,     4, 6, 4, 9
     *    4  7  6  8      4, 6, 8,
     *    4  -  -  1
     *
     *    9, 1, 5,  11
     *    9, 9, 14, 20
     *
     * @param nums -
     * @return -
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        if (len == 2)
            return Math.max(nums[0], nums[1]);

        int[] dp = new int[len];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i<(len - 1); i++) {
            dp[i] = Math.max((nums[i] + dp[i - 2]), dp[i - 1]);
        }

        int max = dp[len - 2];

        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i<len; i++) {
            dp[i] = Math.max((nums[i] + dp[i - 2]), dp[i - 1]);
        }
        if (dp[len - 1] > max)
            max = dp[len - 1];
        return max;
    }

    public static void main(String[] args) {
        int[] input_1 = {2, 3, 2};
        int[] input_2 = {1, 2, 3, 1};
        Tester.createTest(new P213()::rob)
                .addCase(input_1, 3)
                .addCase(input_2, 4)
                .test();
    }

}
